{
 "cells": [
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-05-17T12:53:31.806794Z",
     "start_time": "2024-05-17T12:53:31.780889Z"
    }
   },
   "cell_type": "code",
   "source": [
    "class TreeNode:\n",
    "\tdef __init__(self, data: int):\n",
    "\t\tself.data: int = data\n",
    "\t\tself.flag = False\n",
    "\t\tself.left = None\n",
    "\t\tself.right = None\n",
    "\n",
    "\tdef __str__(self):\n",
    "\t\treturn f\"TreeNode: data={self.data}\"\n",
    "\n",
    "\n",
    "class BinarySearchTree:\n",
    "\tdef __init__(self):\n",
    "\t\tself.root: TreeNode = None\n",
    "\t\tself.flag = False\n",
    "\n",
    "\tdef inordered_tree_walk(self):\n",
    "\t\tself.__inordered_tree_walk(self.root)\n",
    "\n",
    "\tdef __inordered_tree_walk(self, cur: TreeNode):\n",
    "\t\tif cur is not None:\n",
    "\t\t\tself.__inordered_tree_walk(cur.left)\n",
    "\t\t\tprint(cur)\n",
    "\t\t\tself.__inordered_tree_walk(cur.right)\n",
    "\n",
    "\tdef __tree_search(self, key: int, cur: TreeNode) -> TreeNode:\n",
    "\t\tif cur is None or key == cur.data:\n",
    "\t\t\treturn cur\n",
    "\t\tif key < cur.data:\n",
    "\t\t\treturn self.__tree_search(key, cur.left)\n",
    "\t\telse:\n",
    "\t\t\treturn self.__tree_search(key, cur.right)\n",
    "\n",
    "\tdef __iter_tree_search(self, key: int):\n",
    "\t\ttemp = self.root\n",
    "\t\twhile temp is not None:\n",
    "\t\t\tif temp.data == key:\n",
    "\t\t\t\treturn temp\n",
    "\t\t\telif temp.data < key:\n",
    "\t\t\t\ttemp = temp.left\n",
    "\t\t\telse:\n",
    "\t\t\t\ttemp = temp.right\n",
    "\n",
    "\tdef tree_minimum(self, cur: TreeNode = None) -> TreeNode:\n",
    "\t\tcur = self.root if cur is None else cur\n",
    "\t\twhile cur.left is not None:\n",
    "\t\t\tcur = cur.left\n",
    "\t\treturn cur\n",
    "\n",
    "\tdef tree_minimum_recursion(self, cur: TreeNode = None) -> TreeNode:\n",
    "\t\tcur = self.root if cur is None else cur\n",
    "\t\tif cur.left is not None:\n",
    "\t\t\treturn self.tree_minimum_recursion(cur.left)\n",
    "\t\telse:\n",
    "\t\t\treturn cur\n",
    "\n",
    "\tdef tree_maximum(self, cur: TreeNode = None) -> TreeNode:\n",
    "\t\tcur = self.root if cur is None else cur\n",
    "\t\twhile cur.right is not None:\n",
    "\t\t\tcur = cur.right\n",
    "\t\treturn cur\n",
    "\n",
    "\tdef tree_maximum_recursion(self, cur: TreeNode = None) -> TreeNode:\n",
    "\t\tcur = self.root if cur is None else cur\n",
    "\t\tif cur.right is not None:\n",
    "\t\t\treturn self.tree_minimum_recursion(cur.right)\n",
    "\t\telse:\n",
    "\t\t\treturn cur\n",
    "\n",
    "\tdef tree_successor(self, cur: TreeNode) -> TreeNode:\n",
    "\t\tif cur.right is not None:\n",
    "\t\t\treturn self.tree_minimum(cur.right)\n",
    "\t\tpar = self.node_parent(cur)\n",
    "\t\twhile par.right == cur:\n",
    "\t\t\tcur = par\n",
    "\t\t\tpar = self.node_parent(par)\n",
    "\t\treturn par\n",
    "\n",
    "\tdef tree_predecessor(self, cur: TreeNode) -> TreeNode:\n",
    "\t\tif cur.left is None:\n",
    "\t\t\tparent = self.node_parent(cur)\n",
    "\t\t\tif parent is not None:\n",
    "\t\t\t\treturn parent\n",
    "\t\telse:\n",
    "\t\t\treturn self.tree_maximum(cur.left)\n",
    "\n",
    "\tdef node_parent(self, tar: TreeNode, cur: TreeNode = None, left: bool = True,\n",
    "\t                right: bool = True) -> TreeNode | None:\n",
    "\t\tif cur is None:\n",
    "\t\t\tcur = self.root\n",
    "\t\tif (cur.left is not None and cur.left == tar) or (cur.right is not None and cur.right == tar):\n",
    "\t\t\treturn cur\n",
    "\n",
    "\t\tif left:\n",
    "\t\t\tif cur.data <= tar.data:\n",
    "\t\t\t\treturn self.node_parent(tar, cur.right, False, True)\n",
    "\t\t\telse:\n",
    "\t\t\t\treturn self.node_parent(tar, cur.left, True, False)\n",
    "\n",
    "\t\tif right:\n",
    "\t\t\tif cur.data > tar.data:\n",
    "\t\t\t\treturn self.node_parent(tar, cur.left, True, False)\n",
    "\t\t\telse:\n",
    "\t\t\t\treturn self.node_parent(tar, cur.right, False, True)\n",
    "\t\treturn None\n",
    "\n",
    "\tdef tree_insert(self, val: int):\n",
    "\t\tcur = self.root\n",
    "\t\tpost = None\n",
    "\t\twhile cur is not None:\n",
    "\t\t\tpost = cur\n",
    "\t\t\tif val < cur.data:\n",
    "\t\t\t\tcur = cur.left\n",
    "\t\t\telif val > cur.data:\n",
    "\t\t\t\tcur = cur.right\n",
    "\t\t\telse:\n",
    "\t\t\t\tcur = cur.right if self.flag else cur.left\n",
    "\t\t\t\tself.flag = not self.flag\n",
    "\n",
    "\t\tif post is None:\n",
    "\t\t\tself.root = TreeNode(val)\n",
    "\t\telif val <= cur.data:\n",
    "\t\t\tself.root.left = TreeNode(val)\n",
    "\t\telse:\n",
    "\t\t\tself.root.right = TreeNode(val)\n",
    "\n",
    "\tdef transplant(self, p: TreeNode, q: TreeNode):\n",
    "\t\t\"\"\"\n",
    "\t\t以一棵以q为根的子树替换另一棵以p为根的子树（以p为根的子树被以q为根的子树替代了）\n",
    "\t\t\"\"\"\n",
    "\t\tparent = self.node_parent(p)\n",
    "\t\tif parent is None:\n",
    "\t\t\tself.root = q\n",
    "\t\telif p == parent.left:\n",
    "\t\t\tparent.left = q\n",
    "\t\telse:\n",
    "\t\t\tparent.right = q\n",
    "\n",
    "\tdef tree_delete_by_value(self, tar: TreeNode):\n",
    "\t\t\"\"\"\n",
    "\t\t删除一个结点\n",
    "\t\t若删除的结点没有左孩子，直接其右孩子替换掉即可\n",
    "\t\t若删除的结点没有右孩子，直接让其左孩子替换掉即可\n",
    "\t\t若两个孩子都有，从其右子树中找到最小的结点替换掉自己\n",
    "\t\t\t特殊情况下，右子树的最小结点就是右孩子，此时不用修改右孩子的右子树\n",
    "\t\t\t否则就是把这个候选点的左子树\n",
    "\t\t:param tar: 待删除结点\n",
    "\t\t:return: \n",
    "\t\t\"\"\"\n",
    "\t\tif tar.left is None:\n",
    "\t\t\tself.transplant(tar, tar.right)\n",
    "\t\telif tar.right is None:\n",
    "\t\t\tself.transplant(tar, tar.left)\n",
    "\t\telse:\n",
    "\t\t\tcandy = self.tree_minimum(tar.right)\n",
    "\t\t\ttemp_parent = self.node_parent(candy)\n",
    "\t\t\tif temp_parent == tar:\n",
    "\t\t\t\tself.transplant(candy, candy.right)  # 直接让候选结点的右子树替换掉该候选结点\n",
    "\t\t\t\tcandy.right = tar.right  # 因为候选结点为子树的最小结点，故其不存在左子树\n",
    "\t\t\tself.transplant(tar, candy)\n",
    "\t\t\tcandy.left = tar.left\n",
    "\n"
   ],
   "id": "1d28f3c7c832e27c",
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "incomplete input (2020922785.py, line 135)",
     "output_type": "error",
     "traceback": [
      "\u001B[1;36m  Cell \u001B[1;32mIn[1], line 135\u001B[1;36m\u001B[0m\n\u001B[1;33m    \u001B[0m\n\u001B[1;37m    ^\u001B[0m\n\u001B[1;31mSyntaxError\u001B[0m\u001B[1;31m:\u001B[0m incomplete input\n"
     ]
    }
   ],
   "execution_count": 1
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-05-18T13:07:06.801783Z",
     "start_time": "2024-05-18T13:07:06.790284Z"
    }
   },
   "cell_type": "code",
   "source": [
    "class Cardinal:\n",
    "\tdef __init__(self):\n",
    "\t\tself.end = False\n",
    "\t\tself.child:list[Cardinal] = None\n",
    "\t\tself.had = False\n",
    "\n",
    "\tdef post_init(self):\n",
    "\t\tself.child = [Cardinal() for _ in range(26)]\n",
    "\n",
    "\n",
    "class CardinalTree:\n",
    "\tdef __init__(self):\n",
    "\t\tself.root = Cardinal()\n",
    "\t\tself.root.had = True\n",
    "\n",
    "\tdef insert(self, val: str):\n",
    "\t\tcur = self.root\n",
    "\t\tfor i in range(len(val)):\n",
    "\t\t\tindex = ord(val[i]) - ord('a')\n",
    "\t\t\tif cur.child is None:\n",
    "\t\t\t\tcur.post_init()\n",
    "\t\t\tcur = cur.child[index]\n",
    "\t\t\tcur.had = True\n",
    "\t\tcur.end = True\n",
    "\n",
    "\tdef output(self) -> list[str]:\n",
    "\t\t\"\"\"\n",
    "\t\t字典树按字典序输出传入的字符串\n",
    "\t\t\"\"\"\n",
    "\t\tqueue: list[tuple[str, Cardinal]] = [(\"\", self.root)]\n",
    "\t\tans: list[str] = []\n",
    "\t\twhile len(queue) > 0:\n",
    "\t\t\ttemp = queue.pop()\n",
    "\t\t\ttemp_arr = []\n",
    "\t\t\tfor i, item in enumerate(temp[1].child):\n",
    "\t\t\t\tif item.had:\n",
    "\t\t\t\t\ts = temp[0] + chr(ord('a') + i)\n",
    "\t\t\t\t\tif item.end:\n",
    "\t\t\t\t\t\tans.append(s)\n",
    "\t\t\t\t\telse:\n",
    "\t\t\t\t\t\ttemp_arr.append((s, item))\n",
    "\t\t\ttemp_arr.reverse()\n",
    "\t\t\tqueue += temp_arr\n",
    "\t\treturn ans\n",
    "\n",
    "\n",
    "dic = CardinalTree()\n",
    "dic.insert(\"angle\")\n",
    "dic.insert(\"anger\")\n",
    "dic.insert(\"bit\")\n",
    "dic.insert(\"apple\")\n",
    "dic.output()"
   ],
   "id": "5c8e6f649b70def9",
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['anger', 'angle', 'apple', 'bit']"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "execution_count": 70
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
